﻿#pragma once
#include "Index.h"

class IMoveZeros
{
public:
    /**
     * 移动零.
     * https://leetcode.cn/problems/move-zeroes/
     * 数组 双指针
     *
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     */
    virtual void moveZeroes(std::vector<int>& nums) = 0;
};

class MoveZeros
{
public:
    class Exchange:public IMoveZeros
    {
    public:
	    void moveZeroes(std::vector<int>& nums) override
	    {
            if (nums.empty())
                return;
            const int numsSize = nums.size();

            int accept = numsSize;
            for(int i=numsSize-1;i>=0;--i)
            {
				if(nums[i]==0)
				{
                    accept--;
                    for (int k = i; k < accept; ++k)
                        nums[k] = nums[k + 1];
                    nums[accept] = 0;
				}
            }
	    }
    };

    class RemoveZerosThenAppend:public IMoveZeros
    {
    public:
	    void moveZeroes(std::vector<int>& nums) override
	    {
            if (nums.empty())
                return;
            const int numsSize = nums.size();

            int accept = -1;
            for(int i=0;i<numsSize;++i)
            {
	            if(nums[i]!=0)
                    std::swap(nums[i], nums[++accept]);
            }

            const int leftSize = numsSize - accept - 1;
            if (leftSize > 0)
                memset(&nums[accept + 1], 0, sizeof(int) * leftSize);
	    }
    };
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(MoveZerosTest, moveZeros)
{
    TEST_SOLUTION2(IMoveZeros, MoveZeros::Exchange, 
        MoveZeros::RemoveZerosThenAppend, &)
    {
        __slnTestor.setTestTimes(25);

        std::vector<int> nums;

        nums.resize(1000, 0);
        std::vector<int> randNums = TestingUtil::randRangeInts(100, 0, 100);
        nums.insert(nums.end(), randNums.begin(), randNums.end());

    	std::random_device rd;
        std::mt19937 g(rd());
        std::shuffle(nums.begin(), nums.end(), g);

        std::vector<int> expectNums;
        for(int i=0;i<nums.size();++i)
        {
            if (nums[i] != 0)
                expectNums.push_back(nums[i]);
        }
        const int appendZeros = nums.size() - expectNums.size();
        for (int i = 0; i < appendZeros; ++i)
            expectNums.push_back(0);

        solution->moveZeroes(nums);

        EXPECT_EQ(FormatedUtil::dumpFormated(nums), FormatedUtil::dumpFormated(expectNums));
    };
}
#endif